package pers.vic.basics.leetcode;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @description: 55. 跳跃游戏  {@literal https://leetcode-cn.com/problems/jump-game/}
 * @author Vic.xu
 * {@link J0045_H_Jump}
 * @date: 2020/12/16 0016 9:13
 */
public class J0055_M_CanJump {
    /*
    给定一个非负整数数组，你最初位于数组的第一个位置。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    判断你是否能够到达最后一个位置。
     */

    /**
     * 这一题和45题 类似 {@link J0045_H_Jump#jump(int[])} 当然可以用贪心算法；
     * 但是刷题已经一段时间了，我觉得刷过去不是我的目的，我应该尝试一些新的解决方法，而不单纯的刷题目
     */
    /**
     *
     */
    public static boolean canJump(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }

        return greedy(nums);
    }

    /**
     * 再来个贪心算法: 貌似和动态规划思路差的不多，效果不是特别高
     * 3, 2, 1, 0, 4
     * 2, 3, 1, 1, 4
     */
    public static boolean greedy(int[] nums){
        int len = nums.length;
        int max = nums[0];
        int curMax = max;
        for (int i = 1; i < len; i++) {
            //连当前位置都达不到  直接返回false
            if (curMax < i) {
                return false;
            }
            //已经可以达到重点
            if (max >= len) {
                return true;
            }
            int temp = i + nums[i];
            //当前区间内可达的最大值
            curMax = Math.max(temp, curMax);
            if (i == max) {
                max = Math.max(max, curMax);
            }
        }
        return max >= len-1;
    }

    /**
     * 再来个动态规划 完美通过 均超过82%
     */
    public static boolean dp(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1]  < i) {
                return false;
            }
            dp[i] = Math.max(dp[i - 1], nums[i] + i);
        }
        return dp[len - 1] >= nums[len - 1];
    }

    /**
     * 递归算法：可惜当数据特别大的时候 执行时间超额了
     */
    public static boolean recursion(int index, int[] nums, Set<Integer> cache) {
        if (index >= nums.length - 1) {
            return true;
        }
        //历史缓存的不可达的下标
        if (cache.contains(index)) {
            return false;
        }
        //如果当前位置无法再往前走 就结束 (因为上面已经判断过了 此处直接返回false)
        if (nums[index] == 0) {
            return false;
        }
        //原本一个个往上加  但是数据过多的时候 太慢，改为先大步往前走
        for (int i = nums[index]; i >= 1; i--) {
            boolean recursion = recursion(index + i, nums, cache);
            if (recursion) {
                return true;
            } else {
                cache.add(index + i);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        //true
        int[] nums = {2, 3, 1, 1, 4};
        //false
        int[] nums2 = {3, 2, 1, 0, 4};
        System.out.println(canJump(nums));
        System.out.println(canJump(nums2));

    }
}
